package leetcode_core.sort;

import org.junit.Test;

import java.util.Arrays;

public class RandomDemo {

    @Test
    public void test(){
        //Math.random是等概率的
        int testTimes = 10000;
        int count =0;
        for(int i = 0;i<testTimes;i++){
            if(Math.random() < 0.3){
                count++;
            }
        }
        System.out.println((double) count/(double) testTimes);
    }
    @Test
    public void test1(){
        int testTimes = 10000;
        int count =0;
        for(int i = 0;i<testTimes;i++){
            if(f1()==0){//0.4929
                count++;
            }
        }
        System.out.println(((double) count/(double) testTimes));
    }

    private static double xToXPower(){
        return Math.max(Math.random(),Math.random());
    }

    private static double xToXPower3(){
        return Math.max(Math.max(Math.random(),Math.random()),Math.random());
    }

    private static double xToXPowerMin(){
        return Math.min(Math.random(),Math.random());
    }

    public static int f(){
        return (int)(Math.random()*5)+1;
    }

    //随机机制,只能用f1(),等概率返回0和1
    public static int f1(){
        int ans = 0;
        do {
            ans = f();
        }while (ans == 3);
        return ans<3?0:1;
    }

    //得到000-111做到等概率
    public static int f3(){
        return (f1()<<2) + (f1()<<1) + (f1()<<0);
    }

    public static int f4(){
        int ans = 0;
        do {
            ans = f3();
        }while (ans == 7);
        return ans;
    }

    //实战,有一个3~19的等概率发生器,让你实现17~56的等概率发生器
    //3~19,可以简化为0~16,那么取值就是[0,17)
    public static int g1(){
        return (int)(Math.random()*17)+3;
    }

    public static int g2(){
        int ans = 0;
        do {
            ans = g1();
        }while (ans == 11);
        return ans;
    }

    public static int g3(){
        //需要五位
        int ans =  0;
        do {
            ans = (g2()<<4) +(g2()<<3) +(g2()<<2)+(g2()<<1)+(g2()<<0);
        }while (ans >39);
        return ans;
    }

    public int x(){
        return Math.random() < 0.84? 0:1;
    }

    //固定概率返回0和1
    public int y(){
        int ans = 0;
        do {
            ans = x();
        }while (ans == x());
        return ans;
    }

    //返回一个数组arr,arr长度[0,maxLen-1],arr中的每个值[0,maxValue-1]
    public static int[] lenRandomValueRandom(int maxLen,int maxValue){
        int len = (int)(Math.random()*maxLen);//长度随机
        int[] ans = new int[len];
        for(int i = 0;i<len;i++){
            ans[i] = (int)(Math.random()*maxValue);
        }
        return ans;
    }

    public static boolean sorted(int[] arr){
        if(arr.length == 0){
            return true;
        }
        int max = arr[0];
        for (int i =1;i<arr.length;i++){
            if(max > arr[i]){
                return false;
            }
            max = Math.max(max,arr[i]);
        }
        return true;
    }

    public static int[] copyArray(int[] arr){
        int[] ans = new int[arr.length];
        for (int i = 0;i<arr.length;i++){
            ans[i] = arr[i];
        }
        return ans;
    }

    @Test
    public void test2(){
        int maxLen = 50;
        int maxValue = 1000;
        int testTime = 10000;
        for(int i = 0;i< testTime;i++){
            int[] arr1 = lenRandomValueRandom(maxLen,maxValue);
            int[] arr2 =  copyArray(arr1);
            int[] tmp1 =  copyArray(arr1);
            int[] tmp2 =  copyArray(arr2);
            BubbleSort.bubbleSort(arr1);
            InsertSort.insertSort(arr2);
            if(!sorted(arr1)){
                System.out.println("冒泡错了:"+ Arrays.toString(tmp1));
            }
            if(!sorted(arr2)){
                System.out.println("插入错了:"+Arrays.toString(tmp2));
            }
        }
    }






}
